#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <map>
#include <string>
#include <string.h>
using namespace std;

struct TNode {
    char Value;
    TNode *Parent;
    TNode *Left;
    TNode *Right;

    TNode()
        : Value(' ')
        , Parent(0)
        , Left(0)
        , Right(0) {
    }
};

static void LUR(const TNode *node, string &res) {
    if (node->Left)
        LUR(node->Left, res);
    res.push_back(node->Value);
    if (node->Right)
        LUR(node->Right, res);
}

static void ULR(const TNode *node, string &res) {
    res.push_back(node->Value);
    if (node->Left)
        ULR(node->Left, res);
    if (node->Right)
        ULR(node->Right, res);
}

static void LRU(const TNode *node, string &res) {
    if (node->Left)
        LRU(node->Left, res);
    if (node->Right)
        LRU(node->Right, res);
    res.push_back(node->Value);
}

int main() {
    //
    ifstream ifile("input.txt");
    int n;
    ifile >> n;
    vector<TNode> nodes(n);
    for (int i = 0; i < n; ++i) {
        TNode &pnode = nodes[i];
        pnode.Value = char('A' + i);
        char l, r;
        ifile >> l >> r;
        if (l != '-') {
            TNode &lnode = nodes[l-'A'];
            pnode.Left = &lnode;
            lnode.Parent = &pnode;
        }
        if (r != '-') {
            TNode &rnode = nodes[r-'A'];
            pnode.Right = &rnode;
            rnode.Parent = &pnode;
        }
    }
    ifile.close();

    //
    TNode *root = &(nodes[0]);
    while (root->Parent != 0)
        root = root->Parent;

    string resLUR;
    LUR(root, resLUR);
    
    string resULR;
    ULR(root, resULR);

    string resLRU;
    LRU(root, resLRU);

    //
    ofstream ofile("output.txt");
    ofile << resLUR << endl
          << resULR << endl
          << resLRU << endl;
    ofile.close();
    return 0;
}
